1. Field of the Invention
The present invention relates to a method for enhancing a life cycle of memory, more specifically to a method for enhancing a life cycle of memory by setting a level for each data block.
2. Description of the Prior Art
In an electronic device equipped with a flash memory control card, there are several blocks, each of which includes several pages, for writing and erasing data stored in a flash memory of said flash memory control card. Data is stored in majority of a said page whereas related control information of said page is stored in remainder of said page. For example, in a first conventional flash memory, a block contains 64 pages, each of which occupies 2048 bytes for data plus 64 bytes for said control information. In a second conventional flash memory, a block contains 32 pages, each of which includes 512 bytes for data plus 16 bytes for said control information.
Please refer to FIG. 1, FIG. 2, FIG. 3, FIG. 4, and FIG. 5, which are diagrams for illustrating block operations in a flash memory of a conventional flash memory controller. A PBA Block #n stores pages, as shown in FIG. 1, for various logical pages of a plurality of logical blocks. In FIG. 1, another free block PBA Block #m is retrieved from a free queue. In FIG. 2, two pages PBA Page #0 and PBA Page #1, each of which includes data, are copied from the physical block PBA Block #n to the free block PBA Block #m. In FIG. 3, a host writes new data into the free block PBA Block #m at the page PBA Page #2. In FIG. 4, data stored at the pages from PBA Page #3 to PBA Page #31 of the physical block PBA Block #n is written into the free block PBA Block #m at the pages from PBA Page #3 to PBA Page #31. In FIG. 5, at last, all data stored in the physical block PBA Block #n is erased so that the physical block PBA Block #n becomes a new free block for returning to the free queue.
As described above, while executing the abovementioned procedure, each physical block is often erased or written for updating at least one logical page. However, repeatedly writing or erasing to a same physical block for a few logical pages always wears the availability of said same physical block.
Note that in the abovementioned procedure, logical pages of a logical block occupy consecutive logical addresses. However, two logical pages occupying two consecutive logical addresses always occupy two separate physical addresses, both of which are always in different physical blocks. Therefore, updating data in a plurality of logical pages occupying consecutive logical address of a logical block always results in updating a large plurality of physical pages, which are respectively located at different physical blocks (some of the physical pages may be located at a same physical block). For updating large amount of logical pages, a same physical block may have to be updated much frequently because of updating a large plurality of related logical pages, and an availability of said same physical block is worn significantly for the noted reason.
Among available algorithms utilized by common flash controllers, a specific set of physical blocks in the physical memory is frequently written or erased with a higher probability than the other physical blocks in the physical memory, as discussed above. Therefore, after a significant amount of updates on a specific physical block, a write disturbance easily happens to the specific physical block with a high probability of being written and the specific physical block may not be accessed or updated by the host anymore in a hardware aspect. It represents that the life cycle of the specific physical block is thus over.
While such write disturbances accumulate on the physical memory, the availability and the life cycle of the physical memory decreases significantly. Eventually individual disturbances may cause a whole breakdown of the physical memory. The physical memory thus has to be replaced while a lot of physical blocks in the physical memory are still available.
A technique called wear leveling has been proposed for easing such situations. Note that the following diagrams are illustrated in views of blocks, whereas the diagrams from FIG. 1 to FIG. 5 are illustrated in views of pages, for clearer explains. Please refer to FIG. 6, which is a schematic diagram of a prior art wear leveling method. A physical memory includes a plurality of physical blocks. Some physical blocks are mapped to by another plurality of logical blocks while other physical blocks not mapped to by any logical blocks are regarded as free blocks. A corresponding erase count field is disposed along with each of the physical blocks in the physical memory for recording a corresponding number of times that physical block has been modified. As an example, in FIG. 1, the physical memory block notated as “0” is a “Free Block” that has been modified 15235 times. A free queue is utilized for storing corresponding links or pointers of the free blocks and for facilitating the management of the free blocks. The strategy of the prior art wear leveling method is described as follows.
Referring to FIG. 6, every time when a host updates a logical block, or when the host updates at least one logical page in said logical block, a physical block having the smallest modify count excluding the free blocks is chosen for storing the updated data in the logical block. LBA Block #1 is therefore chosen to store the updated data. A free block indicated by the front terminal of the free queue is also retrieved for storing the original data stored in the physical block to be updated. Thus, the free block at memory location “0” is retrieved. First, the retrieved free block stores the original data stored in the physical block to be updated and then the physical block to be updated is erased. At this time, a swap between the free block and the physical block has been completed. The erased physical block is then utilized for storing the updated data in the logical block. The modify count of the updated physical block is also increased by 1 for representing that the physical block has been modified one more time by swapping with the free block. Increasing the modify count by 1 corresponds to a swap between the physical block and the free block.
As time goes on, a physical block having the smallest modify count excluding the free blocks is always the first physical block to be erased and updated in the physical memory, preventing modifications from concentrating in a specific physical block or in a specific set of physical blocks. However, every time when a physical block having the smallest modify count is searched and chosen, it is necessary to scan the whole physical memory to determine the modify counts of the physical blocks mapped by the logical blocks in the physical memory, and the performance impact on the physical memory is thus huge. Bits for storing the modify counts of the physical blocks are also numerous, for example, it takes at least 16 or 17 bits for storing the modify counts as shown in FIG. 6 since 2 to the 15th power equals 32768 and a sign bit is also required for storing the modify counts. Moreover, although the method prevents modifications concentrating in a specific physical block or in a specific set of physical blocks, the probabilities of the physical blocks being modified still vary a lot since when a physical block having the smallest modify count is chosen, the free blocks are not taken into consideration even though the modify counts of the free blocks may be significantly higher or lower.